/*
 * @lc app=leetcode.cn id=229 lang=cpp
 *
 * [229] 求众数 II
 */

// @lc code=start
class Solution
{
public:
    vector<int> majorityElement(vector<int> &nums)
    {
        pair<int, int> a(0, 0), b(0, 0);

        for (int x : nums)
        {
            if (a.second && a.first == x)
            {
                a.second++;
            }
            else if (b.second && b.first == x)
            {
                b.second++;
            }
            else if (a.second == 0)
            {
                a.first = x;
                a.second = 1;
            }
            else if (b.second == 0)
            {
                b.first = x;
                b.second = 1;
            }
            else
            {
                a.second--;
                b.second--;
            }
        }

        a.second = b.second = 0;
        for (int x : nums)
        {
            if (x == a.first)
            {
                a.second++;
            }
            else if (x == b.first)
            {
                b.second++;
            }
        }

        vector<int> ans;
        int n = nums.size();
        if (a.second * 3 > n)
            ans.push_back(a.first);
        if (b.second * 3 > n)
            ans.push_back(b.first);

        return ans;
    }
};
// @lc code=end
